import unittest
import time
import matplotlib.pyplot as plt
import numpy as np
from regular_expression_match import Solution

class TestRegularExpression(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_empty_string(self):
        # 测试空字符串与空模式
        self.assertTrue(self.solution.isMatch("", ""))
        self.assertFalse(self.solution.isMatch("", "a"))
        self.assertTrue(self.solution.isMatch("", "a*"))
        self.assertTrue(self.solution.isMatch("", ".*"))
        print("测试空字符串与空模式成功")

    def test_normal_characters(self):
        # 测试常规字符匹配
        self.assertTrue(self.solution.isMatch("abc", "abc"))
        self.assertFalse(self.solution.isMatch("abc", "abd"))
        self.assertTrue(self.solution.isMatch("a", "a"))
        self.assertFalse(self.solution.isMatch("a", "b"))
        print("测试常规字符匹配成功")

    def test_dot_pattern(self):
        # 测试包含 '.' 的匹配
        self.assertTrue(self.solution.isMatch("abc", "a.c"))
        self.assertTrue(self.solution.isMatch("abc", ".bc"))
        self.assertTrue(self.solution.isMatch("abc", "ab."))
        self.assertTrue(self.solution.isMatch("abc", "..."))
        self.assertFalse(self.solution.isMatch("abc", "a..d"))
        print("测试包含 '.' 的匹配成功")

    def test_star_pattern(self):
        # 测试包含 '*' 的匹配
        self.assertTrue(self.solution.isMatch("aa", "a*"))
        self.assertTrue(self.solution.isMatch("aaa", "a*"))
        self.assertTrue(self.solution.isMatch("", "a*"))
        self.assertTrue(self.solution.isMatch("aab", "c*a*b"))
        self.assertFalse(self.solution.isMatch("aab", "c*a*c"))
        print("测试包含 '*' 的匹配成功")

    def test_mixed_pattern(self):
        # 测试混合 .* 模式
        self.assertTrue(self.solution.isMatch("ab", ".*"))
        self.assertTrue(self.solution.isMatch("abc", ".*"))
        self.assertTrue(self.solution.isMatch("", ".*"))
        self.assertTrue(self.solution.isMatch("abc", "a.*c"))
        self.assertTrue(self.solution.isMatch("abc", ".*c"))
        print("测试混合 .* 模式成功")

    def test_performance(self):
        lengths = [0, 400, 1600, 3200, 6400, 12800]  # 测试不同长度的字符串
        times = []

        print("\n性能测试开始：")
        print("字符串长度\t运行时间(秒)")
        print("-" * 30)

        for length in lengths:
            # 生成测试字符串和模式
            test_string = "a" * length
            pattern = "a*"

            # 测量运行时间
            start_time = time.time()
            self.solution.isMatch(test_string, pattern)
            end_time = time.time()

            # 记录运行时间
            run_time = end_time - start_time
            times.append(run_time)

            print(f"{length}\t\t{run_time:.8f}")

        # 理论时间复杂度曲线
        n = np.array(lengths)
        n_log_n = n * np.log2(n + 1)  # 加1避免 log(0)
        n2 = n ** 2

        def normalize(ref, base):
            return [x / ref[-1] * base[-1] for x in ref]

        # 绘制性能分析图
        plt.figure(figsize=(10, 6))
        plt.plot(lengths, times, 'bo-', label='Measured Time', linewidth=2)
        plt.plot(lengths, normalize(n, times), 'r--', label='O(n)')
        plt.plot(lengths, normalize(n_log_n, times), 'g--', label='O(n log n)')
        plt.plot(lengths, normalize(n2, times), 'm--', label='O(n²)')

        plt.xlabel('Length of input string')
        plt.ylabel('Time (seconds)')
        plt.title('Regex Match Performance Analysis')
        plt.grid(True)
        plt.legend()
        plt.tight_layout()
        plt.show()
        


if __name__ == '__main__':
    unittest.main() 